import { UnionFind } from "./并查集-quickUnion"
// 加权并查集类
export class WeightedUnionFind extends UnionFind {
    protected weighted: number[];// 链接权重
    constructor(size: number) {
        super(size);
        this.weighted = new Array(size + 1).fill(1);// 初始化权重数组，均为1
    }
    // 添加连接通量方法
    union(union: Union): boolean {
        const [point1, point2] = union;
        // 检查输入是否合理
        if (!this.checkInput(point1) || !this.checkInput(point2)) return false;
        // 根据两个触点位置寻找触点的终点位置
        const end1 = this.quickFind(point1);
        const end2 = this.quickFind(point2);
        // 如果两个触点的终点相同说明它们是同一个联通分量，直接返回
        if (end1 === end2) return false;
        // 否则建立新的连通分量，需要考虑加权：总是将小链接插入大链接，保证树的深度尽可能小
        if (this.weighted[end1] > this.weighted[end2]) {// end1链接比end2长时
            this.unionList[end2] = end1;
            this.weighted[end1] += this.weighted[end2];
        } else {
            this.unionList[end1] = end2;// end1链接比end2短时
            this.weighted[end2] += this.weighted[end1];
        }
        this.count--;
        return true;
    }
    // 判断变量是否连通
    isConnected(union: Union): boolean {
        const [point1, point2] = union;
        // 检查输入是否合理
        if (!this.checkInput(point1) || !this.checkInput(point2)) return false;
        return this.quickFind(point1) === this.quickFind(point2);
    }
}


// 测试用例，最大值为9
const uf: WeightedUnionFind = new WeightedUnionFind(9);
uf.union([4, 3]);
uf.union([3, 8]);
uf.union([6, 5]);
uf.union([9, 4]);
uf.union([2, 1]);
uf.union([8, 9]);
uf.union([5, 0]);
uf.union([5, 0]);
uf.union([7, 2]);
uf.union([6, 1]);
uf.union([1, 0]);
uf.union([6, 7]);
console.log(uf.getCount()); // 2
console.log(uf.isConnected([2, 6])); // true
console.log(uf.isConnected([4, 5])); // false
console.log(uf.isConnected([1, 8])); // false
uf.union([1, 8]);
console.log(uf.getCount()); // 1
console.log(uf.isConnected([4, 5])); // true